LDPC codes are linear block codes. The codeword space and the encoding procedure of LDPC codes are specified by a generator matrix G, given by:x=uG
where G is a K×N matrix with full-row rank, u is a 1×K vector representing information bits and x is a 1×N vector for the codeword. Usually, the generator matrix can be written as follows:G=└IK×K PK×(N−K)┘
Alternatively, a linear block code can be equivalently specified by a parity-check matrix H, given byHxt=0
for any codeword x, where H is an M×N matrix, and M=(N−K). Because Hxt=0 implies HGt=0, if a parity-check matrix H is known, so is the generator matrix G, and vice-versa. Matrix G generally describes an encoder, while H is usually used to check if a given binary vector x is a valid codeword in the decoder.
The parity-check matrix H for an LDPC code is sparse, which means a small portion of the entries are one while others are zeros, and the one's positions are determined in a random fashion. These randomly selected positions of one's are critical to the performance of an associated LDPC code, which is analogous to an interleaver of turbo codes.
LDPC code can be represented by a “bipartite” or Tanner graph in which the nodes can be separated into two groups of check nodes and bit nodes with connections allowed only between nodes in differing groups. For example, an LDPC code can be specified by a parity-check matrix, which defines a set of parity-check equations for codeword x as follows:
  H  =            [                                    1                                1                                0                                1                                0                                0                                                0                                1                                0                                0                                1                                1                                                1                                0                                1                                0                                0                                1                                                0                                0                                1                                1                                1                                0                              ]        ⁢                  ⁢    and    ⁢                  ⁢          {                                                                                                                                                      x                        1                                            +                                              x                        2                                            +                                              x                        4                                                              =                    0                                                                                                                                                                  x                        2                                            +                                              x                        5                                            +                                              x                        6                                                              =                    0                                                                                                                                                            x                  1                                +                                  x                  3                                +                                  x                  6                                            =              0                                                                                                            x                  3                                +                                  x                  4                                +                                  x                  5                                            =              0                                          
For a binary LDPC code, all multiplications and additions are defined for binary operations. Consequently, the LDPC code, or more specifically, the parity-check equations can be represented by the Tanner graph of FIG. 1. Each bit node corresponds to a bit in the codeword x, and each check node represents a parity-check equation that is specified by a row of matrix H. Therefore, the bipartite graph for an LDPC code with an M×N parity-check matrix H contains M check nodes and N bit nodes. An edge between a check node and a bit node exists if and only if the bit participates in the parity-check equation associated with the check node.
An LDPC encoder with a code rate of K/N can be implemented as illustrated in FIG. 2. The K information bits are shifted in and stored in K registers. N-K parity bits are calculated according to the sub-matrix P of generator matrix G. The output switch is at position 1 first to serially shift out K information bits, then the switch is connected to position 2 to serially shift out N-K parity check bits.
The LDPC decoder is based on an iterative message-passing, or a “turbo-like” belief propagation. A sum-product algorithm is a well-known method for LDPC decoding and can be implemented in a logarithm domain (see method depicted in FIG. 3). To describe the sum-product algorithm, the following notations can be used: M(b) denoting the set of check nodes that are connected to bit node b, i.e., “1”s positions in the bth column of the parity-check matrix H, and B(m) denoting the set of bit nodes that connect to check node m, i.e., “1”s positions in the mth row of the parity-check matrix. B(m)\b represents the set B(m) with the bit node b excluded. Similarly, M(b)\m represents the set M(b) with the check node m excluded. Variables qb→m0 and qb→m1 denote the probability information that bit node b sends to check node m, indicating P(xb=0) and P(xb=1), respectively. Variables rm→b0 and rm→b1 denote the probability information that the mth check node gathers for the bth bit with a value of 0 and 1, respectively.
Roughly speaking, rm→b0 (or rm→b1) is the likelihood information for xb=0 (or xb=1) from the mth parity-check equation, when the probabilities for other bits are designated by the qb→m's. Therefore, rm→b0 can be considered as the “extrinsic” information for the bth bit from the mth check node. The soft decision or log-likelihood ratio of a bit is calculated by adding a priori probability information to the extrinsic information from all check nodes that connect to it.
In the logarithm domain, all probability information is equivalently characterized by the log-likelihood ratios (LLRs) as follows:
                              L          ⁡                      (                          r                              m                →                b                                      )                          =                  log          ⁢                                    r                              m                →                b                            1                                      r                              m                →                b                            0                                                                        L          ⁡                      (                          q                              b                →                m                                      )                          =                  log          ⁢                                    q                              b                →                m                            1                                      q                              b                →                m                            0                                                                        L          ⁡                      (                          p              b                        )                          =                  log          ⁢                                    p              b              1                                      p              b              0                                                                        L          ⁡                      (                          q              b                        )                          =                  log          ⁢                                    q              b              1                                      q              b              0                                          
where qb0 (or qb1) is an posteriori probability of xb=0 (or xb=1) and pb0 (or pb1) is an priori probability of xb=0 (or xb=1) of received information from a channel. The LDPC decoding procedure described above is summarized in the flowchart in FIG. 3.
In case of high order QAM modulations, each QAM symbol contains multiple code bits while the input to the LDPC decoder is a sequence of LLRs for each bit. Therefore, the received QAM soft symbols must be converted into LLRs for each bit. Assuming the received QAM soft symbol is represented as r=r1+jrQ=s+n, where s=sI+jsQ is its associated QAM hard symbol and n is complex noise with variance 2σ2. The LLR for bit k can be approximated by using a dual-max method as follows:
                                                                        LLR                (                                                                  ⁢                                  b                  k                                )                            =                            ⁢                              ln                ⁢                                                                  ⁢                                                      LL                    ⁢                                          (                                                                                          ⁢                                                                        b                          k                                                =                        1                                            )                                                                            LL                    ⁢                                          (                                                                                          ⁢                                                                        b                          k                                                =                                                  -                          1                                                                    )                                                                                                                                              =                             ⁢                              ln                ⁢                                                                  ⁢                                                                                                                    ⁢                                                                  ∑                                                                                                                                  ⁢                                                                                    b                              k                                                        ⁢                                                                                                                  ∈                                                                                                                  ⁢                                                          S                              1                                                                                                                                                                                                    ⁢                                                                                          ⁢                                              exp                        ⁡                                                  [                                                                                    -                                                                                                                                                                                                        ⁢                                                                                                            (                                                                                                                                                          ⁢                                                                                                                        r                                          I                                                                                -                                                                                  s                                          I                                                                                                                    )                                                                        2                                                                                                                                                                                                                                            ⁢                                                                      2                                    ⁢                                                                                                                                                  ⁢                                                                          σ                                                                                                                                                                                                        ⁢                                        2                                                                                                                                                                                                                                  -                                                                                                                                                                                            ⁢                                                                                                      (                                                                                                                                                  ⁢                                                                                                                  r                                        Q                                                                            -                                                                              s                                        Q                                                                                                              )                                                                    2                                                                                                                                                                                                                              ⁢                                                                  2                                  ⁢                                                                                                                                          ⁢                                                                      σ                                                                                                                                                                                              ⁢                                      2                                                                                                                                                                                                                    ]                                                                                                                                                                                        ⁢                                                                  ∑                                                                                                                                  ⁢                                                                                    b                              k                                                        ⁢                                                                                                                  ∈                                                                                                                  ⁢                                                          S                                                              -                                1                                                                                                                                                        ⁢                                                                                          ⁢                                              exp                        ⁡                                                  [                                                                                    -                                                                                                                                                                                                        ⁢                                                                                                            (                                                                                                                                                          ⁢                                                                                                                        r                                          I                                                                                -                                                                                  s                                          I                                                                                                                    )                                                                        2                                                                                                                                                                                                                                            ⁢                                                                      2                                    ⁢                                                                                                                                                  ⁢                                                                          σ                                                                                                                                                                                                        ⁢                                        2                                                                                                                                                                                                                                  -                                                                                                                                                                                            ⁢                                                                                                      (                                                                                                                                                  ⁢                                                                                                                  r                                        Q                                                                            -                                                                              s                                        Q                                                                                                              )                                                                    2                                                                                                                                                                                                                              ⁢                                                                  2                                  ⁢                                                                                                                                          ⁢                                                                      σ                                                                                                                                                                                              ⁢                                      2                                                                                                                                                                                                                    ]                                                                                                                                                                                            ≈                            ⁢                              K                [                                                                            max                                                                        b                          k                                                ∈                                                  S                          1                                                                                      ⁢                                          {                                                                        -                                                                                    (                                                                                                r                                  I                                                                -                                                                  s                                  I                                                                                            )                                                        2                                                                          -                                                                              (                                                                                          r                                Q                                                            -                                                              s                                Q                                                                                      )                                                    2                                                                    }                                                        -                                                            max                                                                        b                          k                                                ∈                                                  S                                                      -                            1                                                                                                                ⁢                                          {                                                                        -                                                                                    (                                                                                                r                                  I                                                                -                                                                  s                                  I                                                                                            )                                                        2                                                                          -                                                                              (                                                                                          r                                Q                                                            -                                                              s                                Q                                                                                      )                                                    2                                                                    }                                                                      ]                                                                                        =                            ⁢                              K                [                                                                            max                                                                        b                          k                                                ∈                                                  S                          1                                                                                      ⁢                                          {                                                                        2                          ⁢                                                      r                            I                                                    ⁢                                                      s                            I                                                                          -                                                  s                          I                          2                                                +                                                  2                          ⁢                                                      r                            Q                                                    ⁢                                                      s                            Q                                                                          -                                                  s                          Q                          2                                                                    }                                                        -                                                            max                                                                        b                          k                                                ∈                                                  S                                                      -                            1                                                                                                                ⁢                                          {                                                                        2                          ⁢                                                      r                            I                                                    ⁢                                                      s                            I                                                                          -                                                  s                          I                          2                                                +                                                  2                          ⁢                                                      r                            Q                                                    ⁢                                                      s                            Q                                                                          -                                                  s                          Q                          2                                                                    }                                                                      ]                                                                        (        1        )            
where K is the LLR scalar that depends on a noise variance, where S1 and S−1 are sets of (sI sQ) corresponding to bk=1 and −1, respectively. In the present case bk=1 and bk=−1 are equivalent to xbk=0 xbk=1, respectively. In the case of 16QAM (using a bit-to-symbol mapping rule sI=2bk+bk+1 and sQ=2bk+2+bk+3 as an example, where each bit takes a value of 1 or −1), the following equations apply:sI=−3, −1, 1, 3 for (bk, bk+1)=(−1, −1), (−1, 1), (1, −1), (1, 1)sQ=−3, −1, 1, 3 for (bk+2, bk+3)=(−1, −1), (−1, 1), (1, −1), (1, −1) 
The log-likelihood function of bk=1, LL(bk=1), is approximately the largest quantity among eight values determined by {2rIsI−sI2+2rQsQ−sQ2} corresponding to sI>0. Similarly, log-likelihood function of bk=−1 is approximately the largest one among eight quantities of {2rIsI−sI2+2rQsQ−sQ2} evaluated at eight symbols corresponding to sI≦0.
The foregoing description of an LDPC codes can be applied to FEC (Forward Error Correction) applications in many wireless air interfaces such as WiMax (IEEE802.16e), advanced WiFi (IEEE802.11n) and Mobile Broadband Wireless Access (IEEE802.20). Typically, air interfaces such as these utilize Orthogonal Frequency Division Modulation (OFDM) where each tone carries QPSK, 16QAM or 64QAM symbols. During the demodulation process, the soft QAM symbols are converted into LLRs, which feed the LDPC decoder described above. The above-described dual-max method, however, serves to approximate LLR values of each bit. Such approximation can therefore lead to performance degradation.
A need therefore arises for a method and apparatus that improves LDPC decoding.